一、深度优先搜索（Depth-First-Search 简称：DFS）

1.1 遍历过程：

　　（1）从图中某个顶点v出发，访问v。

　　（2）找出刚才第一个被顶点访问的邻接点。访问该顶点。以这个顶点为新的顶点，重复此步骤，直到访问过的顶点没有未被访问过的顶点为止。

　　（3）返回到步骤（2）中的被顶点v访问的，且还没被访问的邻接点，找出该点的下一个未被访问的邻接点，访问该顶点。

　　（4）重复（2） （3） 直到每个点都被访问过，遍历结束。

例无权图：（默认为字母顺序）

　　（1）从顶点A出发，访问该图

　　（2）A的邻接点为BEF 以B为顶点开始访问 B的邻接点有FDC

　　（3）B的所有的点均被访问结束，访问顶点C 顶点C还有F没有被访问

，结束遍历。

故遍历结果为 A->B->C->D->E->F

有向图：（默认为字母顺序）

　　（1）从顶点A出发，访问该图

　　（2）A 的出路顶点为B、D ，从顶点B 开始访问， B的出路只有E 结束此路；

　　（3）开始访问顶点D，D的出路为顶点C和F 此时所有顶点都被遍历了，结束；

故遍历结果为： A->B->E->D->C->F

1.2 算法描述

自然语言：从图中的某个顶点v出发，访问v，并将visited[v]的值为true。

　　　　　 一次检查v的所有邻接点w，如果visited[w]的值为flase，再从w出发进行递归遍历，直到图中的所有顶点都被访问过。

伪代码：

递归算法：

　　visited[MVNum] vexs[i]=v; /*读入顶点信息*/ i++; } g->vexnum=i; /*顶点数目*/ for (i=0;ivexnum;i++) /*邻接矩阵初始化*/ for (j=0;jvexnum;j++) g->arcs[i][j] = 0;/*（1）-邻接矩阵元素初始化为0*/ printf("\n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：\n"); scanf("%d,%d",&i,&j); /*读入边(i,j)*/ while (i!=-1) /*读入i为－1时结束*/ { g->arcs[i][j] = 1; /*（2）-i,j对应边等于1*/ g->arcnum++; scanf("%d,%d",&i,&j); } }/* createGraph */ /*（3）---从第i个顶点出发深度优先搜索，补充完整算法*/ void dfs(int i,graph *g) { int j; printf("%c", g->vexs[i]); visited[i] = TRUE; for (j = 0; j < g->vexnum; j++) if (g->arcs[i][j] == 1 && !visited[j]) dfs(j, g); }/* dfs */ /*深度优先搜索整个图*/ void tdfs(graph *g) { int i; printf("\n从顶点%C开始深度优先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i] != TRUE) /*（4）---对尚未访问过的顶点进行深度优先搜索*/ dfs(i,g); printf("\n"); }/*tdfs*/ /*从第k个顶点广度优先搜索*/ void bfs(int k,graph *g) { int i,j; queue qlist,*q; q=&qlist; q->rear=0; q->front=0; printf("%c",g->vexs[k]); visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while (q->rear!=q->front) /*当队列不为空，进行搜索*/ { i=q->data[q->front]; q->front=(q->front+1)%N; for (j=0;jvexnum;j++) if ((g->arcs[i][j]==1)&&(!visited[j])) { printf("%c",g->vexs[j]); visited[j]=TRUE; q->data[q->rear] = j; /*（5）---刚访问过的结点入队*/ q->rear = (q->rear + 1) % N; /*（6）---修改队尾指针*/ } } }/*bfs*/ /*广度优先搜索整个图*/ void tbfs(graph *g) { int i; printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]); for (i=0;ivexnum;i++) if (visited[i]!=TRUE) bfs(i,g); /*从顶点i开始广度优先搜索*/ printf("\n"); }/*tbfs*/ void init_visit() /*初始化访问标识数组*/ { int i; for (i=0;i